الگوریتم کلونی مورچه ها چیست؟

يک مورچه در حال حرکت، مقداري فرومون (در اندازه­هاي مختلف) از خود بر زمين باقي مي گذارد و بدين ترتيب مسير را بوسيله بوي اين ماده مشخص مي سازد. هنگامي که يک مورچه به طور تصادفي و تنها حرکت مي کند، با مواجه شدن با مسيري که داراي اثر فرومون بيشتري است، به احتمال زياد مسير فوق را انتخاب مي کند و با فروموني که از خود بر جاي مي گذارد، آن را در مسير مذکور تقويت مي نمايد

الگوريتم کلوني مورچه الهام گرفته شده از مطالعات ومشاهدات روي کلوني مورچه هاست. اين مطالعات نشان داده که مورچه ها حشراتي اجتماعي هستند که در کلوني ها زندگي مي کنند و رفتار آنها بيشتر در جهت بقاء کلوني است تادرجهت بقاء يک جزء از آن. يکي از مهمترين و جالبترين رفتار مورچه ها، رفتار آنهابراي يافتن غذا است و بويژه چگونگي پيدا کردن کوتاهترين مسير ميان منابع غذايي وآشيانه. اين نوع رفتار مورچه ها داراي نوعي هوشمندي توده اي است که اخيرا مورد توجهدانشمندان قرار گرفته است.بايد تفاوت هوشمندي توده اي(کلوني) و هوشمندي اجتماعي راروشن کنيم.
در هوشمندي اجتماعي عناصر ميزاني از هوشمندي را دارا هستند. بعنوان مثال درفرآيند ساخت ساختمان توسط انسان، زماني که به يک کارگر گفته ميشود تا يک توده آجررا جابجا کند، آنقدر هوشمند هست تا بداند براي اينکار بايد از فرغون استفاده کند نهمثلا بيل!!! نکته ديگر تفاوت سطح هوشمندي افراد اين جامعه است. مثلا هوشمندي لازمبراي فرد معمار با يک کارگر ساده متفاوت است.
در هوشمندي توده اي عناصر رفتاريتصادفي دارند و بين آن ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنها بصورت غيرمستقيم و با استفاده از نشانه ها با يکديگر در تماس هستند. مثالي در اين مورد رفتارموريانه ها در لانه سازيست.
جهت علاقه مند شدن شما به اين رفتار موريانه ها وتفاوتهوشمندي توده اي و اجتماعي توضيحاتي را ارائه مي دهم :
فرآيند ساخت لانه توسط موريانهها مورد توجه دانشمندي فرانسوي به نام گرس قرار گرفت. موريانه ها براي ساخت لانه سهفعاليت مشخص از خود بروز مي دهند. در ابتدا صدها موريانه به صورت تصادفي به اين طرفو آن طرف حرکت مي کنند. هر موريانه به محض رسيدن به فضايي که کمي بالاتر از سطحزمين قرار دارد شروع به ترشح بزاق مي کنند و خاک را به بزاق خود آغشته مي کنند. بهاين ترتيب گلوله هاي کوچک خاکي با بزاق خود درست مي کنند. عليرغم خصلت کاملا تصادفياين رفتار، نتيجه تا حدي منظم است. در پايان اين مرحله در منطقه اي محدود تپه هايبسيار کوچک مينياتوري از اين گلوله هاي خاکي آغشته به بزاق شکل مي گيرد. پس از اين،همه تپه هاي مينياتوري باعث مي شوند تا موريانه ها رفتار ديگري از خود بروز دهند. در واقع اين تپه ها به صورت نوعي نشانه براي موريانه ها عمل مي کنند. هر موريانه بهمحض رسيدن به اين تپه ها با انرژي بسيار بالايي شروع به توليد گلوله هاي خاکي بابزاق خود مي کند. اين کار باعث تبديل شدن تپه هاي مينياتوري به نوعي ستون مي شود. اين رفتار ادامه مي يابد تا زماني که ارتفاع هر ستون به حد معيني برسد. در اين صورتموريانه ها رفتار سومي از خود نشان مي دهند. اگر در نزديکي ستون فعلي ستون ديگيرينباشد بلافاصله آن ستون را رها مي کنند در غير اين صورت يعني در حالتي که در نزديکياين ستون تعداد قابل ملاحظه اي ستون ديگر باشد، موريانه ها شروع به وصل کردن ستونهاو ساختن لانه مي کنند.
تفاوتهاي هوشمندي اجتماعي انسان با هوشمندي توده ايموريانه را در همين رفتار ساخت لانه مي توان مشاهده کرد. کارگران ساختماني کاملا براساس يک طرح از پيش تعيين شده عمل مي کنند، در حالي که رفتار اوليه موريانه هاکاملا تصادفي است. علاوه بر اين ارتياط مابين کارگران سختماني مستقيم و از طريقکلمات و ... است ولي بين موريانه ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنهابصورت غير مستقيم و از طريق نشانه ها با يکديگر در تماس اند. گرس نام اين رفتار را Stigmergie گذاشت، به معني رفتاري که هماهنگي مابين موجودات را تنهااز طريق تغييرات ايجاد شده در محيط ممکن مي سازد

کد الگوریتم مورچه ها برای حل مسأله فروشنده دوره گرد
الگوریتم بهینه سازی کلونی مورچه ها، و یا به اختصار الگوریتم مورچه ها، از رفتار مورچه های طبیعی که در مجموعه ها بزرگ در کنارهم زندگی می کنند الهام گرفته شده است و یکی از الگوریتم های بسیار کارآمد در حل مسائل بهینه سازی ترکیبی است. الگوریتم های دیگری نیز بر اساس الگوریتم مورچه هاساخته شده اند که همگی سیستم های چند عاملی هستند و عامل ها مورچه های مصنوعی یا به اختصار مورچه هایی هستند که مشابه با مورچه های واقعی رفتار می کنند. الگوریتممورچه ها، یک مثال بارز از هوش جمعی هستند که در آن عامل هایی که قابلیت چندانبالایی ندارند، در کنار هم و با همکاری یکدیگر می توانند نتایج بسیار خوبی به دست بیاورند. این الگوریتم برای حل و بررسی محدوده وسیعی از مسائل بهینه سازی به کاربرده شده است. از این میان می توان به حل مسأله کلاسیک فروشنده دوره گرد و همچنینمسأله راهیابی در شبکه های مخابرات راه دور اشاره نمود.

مساله فروشنده دورهگرد (Traveling Salesman Problem) و یا به اختصار TSP، يكي از مسائل مشهور بهينهسازي تركيبي است. در این مسأله، يك فروشنده دوره گرد مي خواهد به چند شهر سفر کند وكالاي خود را به فروش برساند. اما می بایست از تمام شهرها عبور کند، از هر شهر فقطيك بار عبور كند و با طی کوتاه ترین مسير، سفر خود را به پایان برساند. حل اینمساله کاربردهای وسیعی در حوزه های مختلف مهندسی دارد. از جمله مسائلی که از نظرریاضی با مسأله TSP معادل هستند، می توان به حل انواع مسایل زمانبندی، مسیریابی،جایابی کالا در انبار، جایابی ماشینها در کارگاه ها، و طراحی مدارات چاپی اشارهنمود.


بهينهسازي مسائل بروش کلوني مورچه(ACO) :
همانطور که مي دانيم مسئله يافتن کوتاهترين مسير، يکمسئله بهينه سازيست که گاه حل آن بسيار دشوار است و گاه نيز بسيار زمانبر. بعنوانمثال مسئله فروشنده دوره گرد(TSP). در اين مسئله فروشنده دوره گرد بايد از يک شهر شروع کرده، به شهرهايديگربرود و سپس به شهر مبدا بازگردد بطوريکه از هر شهرفقط يکبار عبور کند و کوتاهترين مسير را نيز طي کرده باشد. اگر تعداد اين شهرها n باشد در حالت کلي اين مسئلهاز مرتبه (n-1)! است که برايفقط 21 شهر زمان واقعا زيادي مي برد:

روز1013*7/1 = S1016*433/2 = ms10*1018*433/2 = !20

با انجام يک الگوريتم برنامهسازي پويا براي اين مسئله ، زمان از مرتبه نمايي بدست مي آيد که آن هم مناسب نيست. البته الگوريتم هاي ديگري نيز ارائه شده ولي هيچ کدام کارايي مناسبي ندارند. ACO الگوريتم کامل و مناسبيبراي حل مسئله TSP است.

مورچه ها چگونه مي توانند کوتاهترين مسير را پيدا کنند؟

مورچه ها هنگام راه رفتن از خود ردي از ماده شيمياييفرومون(Pheromone) بجاي ميگذارند البته اين ماده بزودي تبخير مي شد ولي در کوتاه مدت بعنوان رد مورچه بر سطحزمين باقي مي ماند. يک رفتار پايه اي ساده در مورچه هاي وجود دارد :
آنها هنگام انتخاب بين دو مسيربصورت احتمالاتي( Statistical) مسيري را انتخاب مي کنند که فرومون بيشتري داشته باشد يا بعبارت ديگر مورچه هايبيشتري قبلا از آن عبور کرده باشند. حال دقت کنيد که همين يک تمهيد ساده چگونه منجربه پيدا کردن کوتاهترين مسير خواهد شد :
همانطور که در شکل 1-1 مي بينيم مورچه هاي روي مسير AB در حرکت اند (در دو جهت مخالف) اگر درمسير مورچه ها مانعي قرار ديهم(شکل 2-1) مورچه ها دو راه براي انتخاب کردن دارند. اولين مورچه ازA مي آيد وبهC مي رسد، در مسير هيچفروموني نمي بيند بنابر اين براي مسير چپ و راست احتمال يکسان مي دهد و بطور تصادفيو احتمالاتي مسير CED را انتخابمي کند. اولين مورچه اي که مورچه اول را دنبال مي کند زودتر از مورچه اولي که ازمسير CFD رفته به مقصد مي رسد. مورچه ها در حال برگشت و به مرور زمان يک اثر بيشتر فرومون را روي CED حس مي کنند و آنرا بطور احتمالي و تصادفي( نه حتما و قطعا)انتخاب مي کنند. در نهايت مسير CED بعنوان مسير کوتاهتر برگزيده مي شود. درحقيقت چون طول مسير CED کوتاهتراست زمان رفت و برگشت از آن هم کمتر مي شود و در نتيجه مورچه هاي بيشتري نسبت بهمسير ديگر آنرا طي خواهند کرد چون فرومون بيشتري در آن وجوددارد.
نکه بسيار با اهميت اين استکه هر چند احتمال انتخاب مسير پر فرومون ت توسط مورچه ها بيشتر است ولي اين کماکاناحتمال است و قطعيت نيست. يعني اگر مسير CED پرفرومون تر از CFD باشد به هيچ عنوان نمي شود نتيجه گرفت کههمه مورچه ها از مسيرCED عبورخواهند کرد بلکه تنها مي توان گفت که مثلا 90% مورچه ها از مسير کوتاهتر عبورخواهند کرد. اگر فرض کنيم که بجاي اين احتمال قطعيت وجود مي داشت، يعني هر مورچهفقط و فقط مسير پرفرومون تر را انتخاب ميکرد آنگاه اساسا اين روش ممکن نبود به جواببرسد. اگر تصادفا اولين مورچه مسيرCFD(مسير دورتر) را انتخاب مي کرد و ردي از فرومون بر جاي مي گذاشت آنگاههمه مورچه ها بدنبال او حرکت مي کردند و هيچ وقت کوتاهترين مسير يافته نمي شد. بنابراين تصادف و احتمال نقش عمده اي در ACO بر عهده دارند.
نکتهديگر مسئله تبخير شدن فرومون بر جاي گذاشته شده است. برفرض اگر مانع در مسير AB برداشته شود و فرومون تبخير نشود مورچه ها همان مسيرقبلي را طي خواهند کرد. ولي نظرات شما عزیزان:

نام :

آدرس ایمیل:

وب سایت/بلاگ :

متن پیام:

نظر خصوصی

 کد را وارد نمایید:

 

 

 

عکس شما

آپلود عکس دلخواه: